package com.dataStructure.Dp;

import java.io.InputStream;
import java.math.BigInteger;
import java.util.*;

/**
 * 动态规5部曲
 * 1. 确定dp[i] 的含义
 * 2. 递推公式
 * 3. 初始化数组
 * 4. 遍历数组
 * 5. 确定得到结果
 *
 *  背包问题分类
 *  - 经典01背包，最大价值；能否装满背包，最多装多少
 *  - 装满背包有几种方法
 *  - 问装满背包所有物品的最小个数
 *
 *
 *
 *
 * 01背包:  给你一个能装下质量为 J 的背包，从给出的i含有质量的物品中，每一种物品只能选一个，求怎样选择物品，背包装的重量最重
 * 二维数组版
 *
 *
 * dp[i][j] :表示在 0~i个物品中任取，装进 J 背包的最大价值
 * 在 第i个物品中，要么不取，要么取。
 * 如果不取第i个物品，  则最大价值为    dp[i -1][j]
 * 如果一定取第i个物品  ，则最大价值   dp[i-1][j - weight[i]] + value[i]
 *
 *
 */

public class leetCode {


    public static void main(String[] args) {
        String s = "luolin";
        System.out.println(s.substring(0, 6));
    }


    /**
     * 5. 最长回文子串
     *
     * 中心扩散法
     */
    int max = Integer.MIN_VALUE;
    String results;
    public String longestPalindrome(String s) {

        for (int i = 0; i < s.length(); i++) {
            center2(s,i , i, 0);
            center2(s, i , i+1,0);
        }

        return results;
    }


    public void center2(String s,int i , int j,int len) {
        while(i >=0 && j < s.length()) {
          if (s.charAt(i) == s.charAt(j)) {

              j++;
              i--;
          }
          else {
              break;
          }

        }
        len = j - i -1;

        if (max < len) {
            System.out.println(len);
            max = len;
            results = s.substring(i + 1, j );
        }
    }

    /**
     * 516：最长回文子序列

     */
    public int longestPalindromeSubseq(String s) {
        StringBuilder rs = new StringBuilder(s).reverse();
        int[][] dp = new int[s.length() + 1][s.length() + 1];
        for (int i = 1; i < rs.length(); i++) {
            for (int j = 1; j < s.length(); j++) {
                System.out.println(rs.charAt( i - 1));
                if (rs.charAt(i - 1) == s.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Integer.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }

        return dp[rs.length()][s.length()];
    }

    /**
     * 647； 回文子串
     *
     * 回文子串是中心对称的
     *
     *
     * 中心扩散法
     */
    public int countSubstrings(String s) {
        int result = 0;

        for (int i = 0; i < s.length(); i++) {
            result += center(s, i, i, 0);
            result += center(s,i, i+1,0);
        }
        return result;
    }

    public int center(String s,int i , int j,int result) {
        while(i  >= 0 && j < s.length() ) {
            if (s.charAt(i) == s.charAt(j) ) {
                result++;
                i--;
                j++;
            }
            else {
               return result;
            }


        }
        return result;
    }


    /**
     * 583. 两个字符串的删除操作
     */
    public int minDistance(String word1, String word2) {
        int[][] dp = new int[word1.length() + 1][word2.length() + 1];
        for (int i = 1  ; i < word1.length() + 1; i++) {
            for (int j = 1; j < word2.length() + 1; j++) {
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                }
                else {
                    dp[i][j] = Integer.max(dp[i - 1][j],dp[i][j - 1]);
                }
            }
        }

        int publicLength = dp[word1.length()][word2.length()];

        int result = (word1.length() - publicLength) + (word2.length() - publicLength);

        return result;
    }

    /**
     * 115. 不同子序列
     */
    public int numDistinct(String s, String t) {
        int[][] dp = new int[t.length() + 1][s.length() + 1];

        for (int i = 0;i < s.length() + 1; i++) {
            dp[0][i] = 1;

        }
        for (int i = 1; i < t.length() + 1; i++) {
            dp[i][0] = 0;
        }

        for (int i = 1; i < t.length() + 1; i++) {
            for (int j = 1; j < s.length() + 1; j++) {
                if (t.charAt(i - 1) == s.charAt(j - 1)) {
                    dp[i][j] = dp[i][j - 1] + dp[i - 1][j - 1];
                }
                else {
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }

        return dp[t.length()][s.length()];
        //加一个为空的情况
    }


    /**
     * 判断子序列
     */
    public boolean isSubsequence(String s, String t) {
        int i = 0;
        int j = 0;
        for (; i < t.length() && j < s.length(); i++) {
            if (t.charAt(i) == s.charAt(j)) {
                j++;
            }
        }

        return j == s.length();
    }


    /**
     * 53. 最大子数组和
     *
     * dp[i] 以 结尾的最大子数组和
     */
    public int maxSubArray(int[] nums) {
        //z + (s - f) =
        int[] dp = new int[nums.length];

        dp[0] = nums[0];
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < nums.length; i++) {
            if (dp[i -1] >= 0) {
                dp[i] = nums[i] + dp[i -1];
            }
            else {
                dp[i] = nums[i];
            }

            max = Integer.max(max,dp[i]);
        }

        return max;
    }


    /**
     * 1035. 不相交的线
     */
    public int maxUncrossedLines(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];

        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i - 1] == nums2[j - 1]) {
                    dp[i][j] = dp[i - 1][j -1] + 1;
                }
                else {
                    dp[i][j] = Integer.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        return dp[nums1.length][nums2.length];
    }
    /**
     * 1143. 最长公共子序列
     * 还是用网格画法
     */
    public int longestCommonSubsequence(String text1, String text2) {
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 1; i < text1.length() + 1; i++) {
            for (int j  = 1;j < text2.length() + 1; j++) {
                if (text1.charAt(i -1) == text2.charAt(j -1)) {
                    dp[i][j] = dp[i -1][j -1] + 1;
                }
                else {
                    dp[i][j] = Integer.max(dp[i -1][j],dp[j -1][i]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }

    /**
     * 718. 最长重复子数组
     *
     * dp[i][j]：nums1中前i个字符和nums2中前j个字符  的最长重复子数组
     */
    public int findLength(int[] nums1, int[] nums2) {
        int[][] dp = new int[nums1.length + 1][nums2.length + 1];
        int max = 0;
        for (int i = 1; i < nums1.length + 1; i++) {
            for (int j = 1; j < nums2.length + 1; j++) {
                if (nums1[i -1] == nums2[j -1]) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                    max = Integer.max(dp[i][j],max);
                }
                else {
                    dp[i][j] = 0;
                }
            }
        }

        return max;
    }

    /**
     * 674. 最长连续递增序列
     *
     * dp[i] ：一字符nums[i]结尾的最长连续递增子序列
     */
    public int findLengthOfLCIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);

        for (int i = 1; i < dp.length; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i] && j + 1== i) {
                    dp[i] = Integer.max(dp[i],dp[j] + 1);
                }
            }
        }
        int  max = 0;
        for (int e : dp) {
            max = Integer.max(e,max);
        }
        return max;

    }

    /**
     * 300. 最长递增子序列
     *
     * dp[i]： 以nums[i]字符结尾的最大递增子序列的长度，
     */
    public int lengthOfLIS(int[] nums) {
        int[] dp = new int[nums.length];
        Arrays.fill(dp,1);
        for (int i = 1; i < nums.length;i++) {
            for (int j = 0; j < i; j++) {
                if (nums[j] < nums[i]) {
                    dp[i] =Integer.max( dp[j] + 1,dp[i]);
                }
            }
        }
        int max = 0;
        for (int e :dp){
            max = Integer.max(e,max);
        }
        return max;
    }


//    /**
//     * 121. 买股票的最佳时机
//     *
//     *
//     */
//    public int maxProfit(int[] prices) {
//
//    }


    /**
     * 213. 打家劫舍2
     *
     * dp[i] 前i个房子，可以偷窃到的最大金额
     *
     * 因为是环形，就有两种情况
     *
     */
    public int rob2(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        //选第一个，不选最后一个
        int[] dp = new int[nums.length ];
        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i <= nums.length - 1; i++) {
            int yes = nums[i - 1] + dp[i -2];
            int no = dp[i -1];
            dp[i] = Integer.max(yes,no);
        }

        //选最后一个，不选第一个

        int[] num2 = Arrays.copyOfRange(nums, 1, nums.length);
        System.out.println(Arrays.toString(num2));
        int[] dp2 = new int[num2.length + 1];
        dp2[0] = 0;
        dp2[1] = num2[0];
        for (int i = 2; i < num2.length + 1; i++) {
            int yes = num2[i -1] + dp2[i -2];
            int no = dp2[i -1];
            dp2[i] = Integer.max(yes,no);
        }

        return Integer.max(dp[nums.length -1],dp2[num2.length]);
    }

    /**
     * 198.打家劫舍
     *
     *  dp[i] ：第i个房间，偷到的最高金额
     *  dp[i]：由前 i -2 个房间可以推出，
     *  最后取dp的最大值
     *
     *  有点爬楼梯的思想：
     *
     */
    public int rob(int[] nums) {
        int[] dp = new int[nums.length + 1];

        dp[0] = 0;
        dp[1] = nums[0];
        for (int i = 2; i < nums.length + 1; i++) {
            int cur = nums[i - 1];
            int max = Integer.MIN_VALUE;
            for (int j = i -2 ; j >=0; j--) {
                max = Math.max(dp[j], max);
            }
            dp[i] = cur + max;
        }
        int max = Arrays.stream(dp).reduce(Integer.MIN_VALUE, Integer::max);
        return max;
    }




    /**
     * 139, 单词拆分
     *
     * 定义 dp[i] : 字符串的前i个字符可以被字典的单词拼接出来
     *
     * 序列问题，常用 subString
     *
     */
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] dp = new boolean[s.length() + 1];
        HashSet<String> set = new HashSet<>(wordDict);
        dp[0] = true;

        for (int i = 1; i < s.length() + 1; i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j]  && set.contains(s.substring(j,i ))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
    }

    /**
     * 279 完全平方数
     * 完全背包
     *
     * 背包容量：目标n
     * 物品重量：i的平方
     * 物品价值：1
     *
     * dp[i][j]：前i个数，凑出平方和为 j的最小个数
     */
    public int numSquares(int n) {

        //初始化一个大值

        List<Integer> list = new ArrayList<>();
        int t = 1;
        while (t * t <= n) {
            list.add(t * t);
            t++;
        }
        int[][] dp = new int[list.size() + 1][n + 1];
        Arrays.fill(dp[0], INF);

        dp[0][0] = 0;
        for (int i = 1; i <= list.size() ; i++) {
            int x = list.get(i - 1);
            for (int j = 0; j <= n; j++) {
                // 对于不选第 i 个数的情况

                dp[i][j] = dp[i - 1][j];
                // 对于选 k 次第 i 个数的情况
                for (int k = 1; k * x <= j; k++) {
                    // 能够选择 k 个 x 的前提是剩余的数字 j - k * x 也能被凑出
                    if (dp[i - 1][j - k * x] != INF) {
                        dp[i][j] = Math.min(dp[i][j], dp[i - 1][j - k * x] + k);
                    }
                }
            }
        }
        return dp[list.size()][n];
    }


    /**
     * 322. 零钱兑换
     *
     *  背包容量：总金额
     *  物品价值：硬币个数
     *  物品重量：yiying
     *  由于取得是最小值，所以就的初始化一个大值
     *  */


    public int coinChange(int[] coins, int amount) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        for(int i=0;i<coins.length+1;i++){
            for(int j=0;j<amount+1;j++){
                dp[i][j]=amount+1;
            }
        }
        dp[0][0]=0;
        for (int i = 1; i < coins.length + 1; i++) {
            int v = coins[i - 1];
            for (int j = 0; j < amount + 1; j++) {
                dp[i][j]=dp[i-1][j];
                for (int k = 1; k * v <= j; k++) {

                    dp[i][j] = Math.min(dp[i - 1][j - k * v] + k, dp[i][j]);

                }
            }
        }
        return dp[coins.length][amount]==amount+1?-1:dp[coins.length][amount];
    }

    /**
     * 377 组合总和IV 完全背包
     * 由于这个是排列，所以外循环需要遍历背包，而内循环要遍历物品
     * 可以直接使用爬楼梯的思路
     * dp[i][j]
     */
    public int combinationSum4(int[] nums, int target) {
        int[] ar = new int[target + 1];
        ar[0] = 1;
        for (int i = 1;i < nums.length + 1; i++) {
            for (int num : nums) {
                if (i - num <0 ) {
                    continue;
                } else {
                    ar[i] += ar[i - num];
                }
            }
        }
        return ar[target];
    }


    /**
     *  518：零钱兑换
     *  抽象完全背包
     *
     *  1. 背包的总容量·  ： amount
     *  2. 物品的重量：coins[i]
     *  3. 物品的价值： coins[i]
     *  4. dp[i][j]  前i个零钱中，装满重量为j的背包的  方案数
     *
     *
     *  方案数不需要加 所谓的 value[i]
     *
     */
    int INF = Integer.MAX_VALUE;
    public int change(int amount, int[] coins) {
        int[][] dp = new int[coins.length + 1][amount + 1];
        dp[0][0] = 0;
        for(int i=0;i<coins.length+1;i++){
            for(int j=0;j<amount+1;j++){
                dp[i][j]=amount+1;
            }
        }

        for (int i = 1; i < coins.length + 1; i++) {
            for (int j = 0; j < amount + 1; j++) {
                dp[i][j]= dp[i - 1][j];

                for (int z = 1; z * coins[i -1] <= j; z++) {
                    if (dp[i -1][j - z * coins[i -1]] != Integer.MAX_VALUE) {
                        int yes = dp[i - 1][j - z * coins[i - 1]] + z;
                        dp[i][j] = Math.min(dp[i][j], yes);
                    }
                }
                System.out.println(dp[i][j]);
            }
        }
        return dp[coins.length][amount] == amount + 1 ? -1:dp[coins.length][amount];
    }
    /**
     *
     *
     * 力扣 ：1 和 0
     *
     * 抽象 01背包问题
     * 背包容量：m个0，n个1
     * 物品重量：字符 ’1‘ 或 ‘0’ 的个数
     * 物品价值：最大子集的长度
     *
     */
    public int findMaxForm(String[] strs, int m, int n) {
        int[][] cnts = new int[strs.length][2];

        for (int i = 0; i < cnts.length;i++) {
            int zero = 0;
            int one = 0;
            for (int j = 0; j < strs[i].length(); j++) {
                if (strs[i].charAt(j) == '0') {
                    zero ++;
                } else {
                    one++;
                }
            }
            cnts[i] = new int[]{zero,one};
        }
        int[][][] dp = new int[strs.length + 1][m + 1][n + 1];


        for (int i = 1; i <= strs.length; i++) {
            int curZero = cnts[i -1][0];
            int curOne = cnts[i -1 ][1];
            for (int j = 0; j < m + 1; j++) {
                for (int z = 0; z < n + 1; z++) {
                    //不选当前物品
                    int no = dp[i - 1][j][z];
                    int yes;
                    //选择当前物品
                    if (curZero <= m && curOne <= n) {
                        yes = dp[i - 1][j - curZero][j - curOne] + 1;
                    } else
                       yes = 0;

                    dp[i][j][z] = Math.max(yes,no);
                }
            }
        }
        return dp[strs.length][m][n];
    }

    /**
     * 目标和
     * @param nums
     * @param target
     * @return
     */

    public int findTargetSumWays(int[] nums, int target) {
      int sum = Arrays.stream(nums).sum();
      Arrays.sort(nums);
      if (sum % target != 0) {
          return 0;
      }
      sum  = (sum - target) /2;

      backTracing(nums,0,0,sum);
      return result.size();
    }
    LinkedList<Integer> list = new LinkedList<>();
    List<List<Integer>> result = new ArrayList<>();


    public  void backTracing(int[] nums,int index,int s1, int sum) {
        if (s1 > sum ) {
            return;
        }
        if (s1 == sum) {
            result.add(new ArrayList<>(list));
            return;
        }

        for (int i = 0;i < nums.length; i++) {
            list.add(nums[i] );
            s1+=nums[i];
            backTracing(nums,i+1,s1,sum);
            s1-=nums[i];

            list.removeLast();

        }
    }

    /**
     * 分割等和子集
     * @param nums
     * @return
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int e : nums) {
            sum +=e;
        }
        if (sum % 2 != 0) {
            return false;
        }
        sum = sum/2;

        int[][] dp = new int[nums.length][sum +1];

        for (int i = nums[0]; i < sum + 1; i++) {
            dp[0][i] = nums[0];
        }
        for (int i = 1; i < nums.length ; i++) {
            for (int j = 1; j < sum + 1;j ++) {
                if ( j < nums[i]) {
                    dp[i][j] = dp[i -1][j];
                } else {
                    dp[i][j]  = Integer.max(dp[i -1][j],dp[i-1][j - nums[i]] + nums[i]);
                }
            }
        }

        return dp[nums.length -1][sum] == sum;
    }


//    public class Main {
//        public static void main(String[] args) {
//            Scanner in = new Scanner(System.in);
//            int n = in.nextInt();
//            int w = in.nextInt();
//            int[][] dp = new int[n][w +1];
//
//            int[] weight = new int[n];
//            int[] value = new int[n];
//            for (int i = 0; i < n;i++) {
//                weight[i] = in.nextInt();
//                value[i] = in.nextInt();
//            }
//
//            // dp[i][j] = Max(dp{i-1][j],dp[i-1][j-weight[i] + value[i])
//            //第二步，初始化数组：
//            //因为每一竖是单调递增，所以
//            for (int i = weight[0]; i < w +1; i++) {
//                dp[0][i] = value[0];
//            }
//
//            //因为第0个物品已经初始化,
//            for (int i = 1; i < n; i++) {
//                for (int j = 1;j < w + 1; j++) {
//                    if(j < weight[i]) {
//                        dp[i][j] = dp[i -1][j];
//                    } else {
//                        dp[i][j] = Integer.max(dp[i-1][j],dp[i-1][j -weight[i]] + value[i]);
//                    }
//
//                }
//
//            }
//
//            System.out.println(dp[n-1][w]);
//
//
//        }
//    }


    /**
     * 不同路径二
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//        int[][] ar = new int[obstacleGrid.length][]
        int m = obstacleGrid.length;
        int n = obstacleGrid[0].length;
        int[][] ar = new int[m][n];
        for (int i = 0; i < m;i++) {
            if (obstacleGrid[i][0] == 0) {
                ar[i][0] = 1;
            } else
                break;;
        }

        for (int j = 0; j < n; j++) {
            if (obstacleGrid[0][j] == 0) {
                ar[0][j] = 1;
            } else
                break;;
        }

        for (int i = 1; i < m; i++) {
            for (int j = 1;  j < n; j++) {
                if(obstacleGrid[i][j]==0) {
                    ar[i][j] = ar[i-1][j] + ar[i][j-1];
                }
            }
        }
        return ar[m -1][n -1];
    }


    public static int uniquePaths(int m, int n) {
//        int n1 = m + n - 2;
//
//        int k = m -1;
//        long result = 1;
//        for (int i = 1; i <= k; i++) {
//            result = result  * (n1 - i + 1) /i;
//        }
//        return (int) result;
        int N1 = m + n -2;

        int k = m -1;
        BigInteger result = BigInteger.valueOf(1);
        for (int i = 1; i <= k; i++) {
            result = result.multiply(BigInteger.valueOf(N1 - i +1)).divide(BigInteger.valueOf(i));

        }
        return result.intValue();
    }

    /**
     * 使用最小花费爬楼梯
     */
    public int minCostClimbingStairs(int[] cost) {
        int len = cost.length;
        int[] dp = new int[len + 1];
        // 从下标为 0 或下标为 1 的台阶开始，因此支付费用为0
        dp[0] = 0;
        dp[1] = 0;
        // 计算到达每一层台阶的最小费用
        for (int i = 2; i <= len; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

        return dp[len];

    }




    /**
         力扣  70，爬楼梯
     */
    public int climbStairs(int n) {
        List<Integer> list = new ArrayList<>(n);
        list.add(1);
        list.add(2);

        for (int i = 2; i < n; i++) {
            int wayCt = list.get(i-1) + list.get(i -2);
            list.add(wayCt);
        }
        return list.get(n -1);
    }
}
